# INF = 0x3f3f3f3f  # 无穷大
# max_size = 100
# dist = [int] * max_size
# s = [bool] * max_size
# path = [int] * max_size
#
#
# class Edge:
#     def __init__(self, head, tail, lowcost):
#         self.head = head  # 边的始点
#         self.tail = tail  # 边的终点
#         self.lowcost = lowcost  # 边上的权值
#
#
# class AMGraph:
#     def __init__(self):
#         self.vexs = []  # 顶点表
#         self.arcs = []  # 邻接矩阵
#         self.vexnum = 0  # 图的当前点数
#         self.arcnum = 0  # 图的当前边数
#
#     def locate_vex(self, name):
#         # 定位顶点在顶点数组中的下标
#         for i in range(0, self.vexnum):
#             if self.vexs[i] == name:
#                 return i
#
#     def create_dn(self):
#         # 采用邻接矩阵表示法，创建无向网
#         self.vexnum = int(input())  # 输入总顶点数
#         self.arcnum = int(input())  # 输入总边数
#         for i in range(0, self.vexnum):
#             vexname = input()
#             self.vexs.append(vexname)
#         self.arcs = [[INF for i in range(self.vexnum)] for i in range(self.vexnum)]  # 初始化邻接矩阵，边的权值均置为无穷大
#         for k in range(0, self.arcnum):  # 构造邻接矩阵
#             v1 = input()
#             v2 = input()
#             w = int(input())  # 输入一条边依附的顶点及权值
#             i = self.locate_vex(v1)
#             j = self.locate_vex(v2)  # 确定v1和v2在图中的位置，即顶点数组的下标
#             self.arcs[i][j] = w  # 边<v1,v2>的权值为w
#
#
# def show_path(graph, begin, end):
#     # 递归显示最短路径
#     if path[end]!= -1:
#         show_path(graph, begin, path[end])
#         print(graph.vexs[path[end]], end="-->")
#
#
# def shortest_path_dij(graph, v0):
#     # 用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径
#     n = graph.vexnum  # n为graph中顶点的个数
#     for v in range(n):  # n个顶点依次初始化
#         s[v] = False  # S初始为空集
#         dist[v] = graph.arcs[v0][v]  # 将v0到各个终点的最短路径长度初始化为弧上的权值
#         if dist[v] < INF:
#             path[v] = v0  # 如果v0和v之间有弧，则将v的前驱置为v0
#         else:
#             path[v] = -1  # 如果v0和v之间无弧，则将v的前驱置为-1
#     s[v0] = True  # 将v0加入S
#     dist[v0] = 0  # 源点到源点的距离为0
#     for i in range(1, n):  # 辅助数组，表示各顶点自成一个连通分量
#         min = INF
#         for w in range(n):
#             if not s[w] and dist[w] < min:
#                 v = w
#                 min = dist[w]  # 选择一条当前的最短路径，终点为v
#         s[v] = True  # 将v加入S
#         for w in range(n):  # 更新从v0出发到集合V−S上所有顶点的最短路径长度
#             if not s[w] and (dist[v] + graph.arcs[v][w] < dist[w]):
#                 dist[w] = dist[v] + graph.arcs[v][w]  # 更新dist[w]
#                 path[w] = v  # 更改w的前驱为v
#
#
# if __name__ == '__main__':
#     G = AMGraph()
#     G.create_dn()
#     print("邻接矩阵表示法创建的无向网矩阵为：")
#     for i in range(0, G.vexnum):
#         for j in range(0, G.vexnum):
#             if j!= G.vexnum - 1:
#                 if G.arcs[i][j] < INF:
#                     print(G.arcs[i][j], end="\t")
#                 else:
#                     print("∞\t", end="")
#             else:
#                 if G.arcs[i][j] < INF:
#                     print(G.arcs[i][j])
#                 else:
#                     print("∞")
#     print("请输入起始点、终点名：")
#     start = input()
#     end = input()
#     start_num = G.locate_vex(start)
#     end_num = G.locate_vex(end)
#     shortest_path_dij(G, start_num)  # 克鲁斯卡尔算法求最小生成树
#     print("生成的最短路径为：")
#     show_path(G, start_num, end_num)  # 输出最短路径
#     print(end)



MAX_SIZE = 100


class SqQueue:
    def __init__(self):
        # 初始化一个空队列
        self.elem = [None] * MAX_SIZE  # 为队列分配一个最大容量为MAX_SIZE的数组空间
        self.front, self.rear = 0, 0  # 头指针和尾指针置为零，队列为空
        self.MAX_SIZE = MAX_SIZE

    def __len__(self):
        # 返回队列的元素个数，即队列的长度
        return (self.rear - self.front + self.MAX_SIZE) % self.MAX_SIZE

    def en_queue(self, e):
        # 把元素e加入队尾
        if (self.rear + 1) % self.MAX_SIZE == self.front:
            # 尾指针在循环意义上加1后等于头指针，表明队满
            raise Exception('队列已满')
        self.elem[self.rear] = e  # 新元素插入队尾
        self.rear = (self.rear + 1) % self.MAX_SIZE  # 队尾指针加1

    def de_queue(self):
        # 删除队头元素并将其返回
        if self.front == self.rear:  # 队空
            raise Exception('队列已空')
        e = self.elem[self.front]  # 保存队头元素
        self.front = (self.front + 1) % self.MAX_SIZE  # 队头指针加1
        return e

    def get_head(self):
        # 返回队头元素，不修改队头指针
        if self.front!= self.rear:  # 队列非空
            return self.elem[self.front]  # 返回队头元素的值，队头指针不变
        else:
            raise Exception('队列已空')

    def queue_empty(self):
        return self.__len__() == 0


INF = 0x3f3f3f3f  # 无穷大


class AMGraph:
    def __init__(self):
        self.vexs = []  # 顶点表
        self.arcs = []  # 邻接矩阵
        self.vexnum = 0  # 图的当前点数
        self.arcnum = 0  # 图的当前边数

    def locate_vex(self, name):
        # 定位顶点在顶点数组中的下标
        for i in range(0, self.vexnum):
            if self.vexs[i] == name:
                return i

    def create_udn(self):
        # 采用邻接矩阵表示法，创建无向网
        self.vexnum = int(input())  # 输入总顶点数
        self.arcnum = int(input())  # 输入总边数
        for i in range(0, self.vexnum):
            vexname = input()
            self.vexs.append(vexname)
        self.arcs = [[INF for i in range(self.vexnum)] for i in range(self.vexnum)]  # 初始化邻接矩阵，边的权值均置为无穷大
        for k in range(0, self.arcnum):  # 构造邻接矩阵
            v1 = input()
            v2 = input()
            w = int(input())  # 输入一条边依附的顶点及权值
            i = self.locate_vex(v1)
            j = self.locate_vex(v2)  # 确定v1和v2在图中的位置，即顶点数组的下标
            self.arcs[i][j] = w  # 边<v1,v2>的权值为w
            self.arcs[j][i] = self.arcs[i][j]  # 置<v1,v2>的对称边<v2,v1>的权值为w


visited = [False] * 1000
level = [0] * 1000


def six_degree_bfs(graph, v):
    # 通过广度优先搜索方法遍历graph来验证六度空间理论，v为指定的一个起点
    visited[v] = True
    q = SqQueue()  # 辅助队列q初始化，置空
    q.en_queue(v)  # v进队
    visit_num = 1
    level[0] = 1
    for len in range(0, 6):
        if not q.queue_empty():
            for i in range(0, level[len - 1]):
                u = q.de_queue()
                for w in range(0, graph.vexnum):
                    if visited[w] is False and graph.arcs[u][w] < INF:
                        visited[w] = True
                        visit_num += 1
                        level[len] += 1
                        q.en_queue(w)
    print(100 * visit_num / graph.vexnum)


if __name__ == '__main__':
    g = AMGraph()
    g.create_udn()
    print("无向连通图从第一个结点开始的广度优先遍历结果为：")
    six_degree_bfs(g, 0)